前言

什麼是LeetCode？

LeetCode是一個求職者經常會使用的線上解題系統，LeetCode網站中的Study Plan提供了求職者經過主題分類後的題目整理，本次的主題就是Study Plan中的LeetCode 75。

• LeetCode Study Plan

什麼又是LeetCode 75？

LeetCode 75來源於Blind 75，Blind 75是由Facebook工程師 Yangshun 所發表的一組包含75道LeetCode題目的清單，最初發表於 Blind 社群，所以被很多人稱為：Blind 75，由於它幾乎涵蓋了演算法及資料結構中常見的知識點，非常適合想要快速掌握面試知識時拿來練習。

個人猜想LeetCode以Blind 75的題目為基礎設計了LeetCode 75，兩者題目選擇相似但並非完全相同，LeetCode 75是一個有三個等級(Level 1、Level 2及Level 3)的學習計畫(Study Plan)，讓使用者每天進行2-3題；今年鐵人賽希望記錄用C語言走過LeetCode 75 Level 1的題目總共是30題 (20題Easy及10題Medium)。

• 分享 Blind 75 作者 Yangshun 建立的新清單，有 75 題，分 5 週（五大主題）。
  • Best practice questions
• 分享作者 Yangshun 建立的網站，可以依個人每周投入的時間客製化學習計畫。
  • Grind 75 questions

為什麼要使用C語言？

除了身為一個每天用C語言的韌體工程師以外，如果查詢網路上的解題資料，解答常常是以C++、Java或Python寫成，這些語言都有許多的容器和內建函數可以使用，用C語言沒有這些東西就會多了點自己造輪子的成就感。

接下來每天會如何進行?

每天會以LeetCode 75 Level 1中的一個題目作為對象，會針對題目做解釋和說明個人的想法、嘗試過的方向、經歷的錯誤等等，最後提供可通過的C語言程式碼。過程中也會參考網路上已有的解法，部分題目由於過於簡單導致篇幅會比較短，這時候就會從Level 2相同知識領域中拿一題來進行說明，所以每天會解答至少是一題至多是二題。

請問你是?

哈囉哈囉，大家好！我是Eric，一個韌體工程師，工作內容是撰寫車輛子系統的控制程式還有進行測試。
若系列文章中有錯字、寫錯或是有任何想討論的地方，請不吝留言告訴我！

第一天不是只有前言嗎? 第一週不是讓大家買書嗎?

由於計畫是30天進行30+題，所以第一天就要開始了！！

LeetCode 75 Level 1 - Day 1 Prefix Sum

1480. Running Sum of 1d Array題目

• 題目連結
• 難易度：Easy

題目敘述

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).
Return the running sum of nums.

預設函數

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* runningSum(int* nums, int numsSize, int* returnSize){

}

題目輸入限制

解題過程

本題是 Day 1 Prefix Sum 中的第一題，主題都是輸入一個陣列，然後回傳計算好的值或是另一個陣列，這題非常容易，但是若是一開始接觸時，會不太了解題目中C語言預設函數的設定，後續題目也常常會遇到要處理陣列的輸入和輸出，以下進行說明：

• 預設函數回傳值是輸出計算結果的陣列指標
• 要先建立動態記憶體再回傳陣列指標，若是在函數內宣告靜態陣列在函數結束後就不存在了，無法傳遞出該陣列的指標
• int* nums 是題目輸入要計算的陣列, numsSize 是該陣列的大小
• int* returnSize 是要提供輸出陣列的大小
• 記得 C 語言透過指標將陣列傳遞時都要再提供陣列的大小，不然對方只知道陣列的位置其實無法得知該陣列的大小

接下來由題目的敘述知道，我們只要把輸入陣列的第[i]項和第[i]項之前的值都加起來成為輸出陣列的第[i]項，如圖Fig. 2所示，輸出的第[i]項還可以寫成輸出的第[i - 1]項加上輸入的第[i]項。

程式碼上傳

int* runningSum(int* nums, int numsSize, int* returnSize){
    int sum = 0;    
    int* dynArr = (int *)malloc(numsSize * sizeof(int));

    *dynArr = *nums;
    for (int i=1; i<numsSize; i++) {
        *(dynArr+i) = *(nums+i) + *(dynArr+i-1);
    }
    *returnSize = numsSize;  // 要回傳陣列的大小，和輸入陣列的大小相同
    return dynArr;
}

第一天就到這邊結束，謝謝大家。